有一个长为 n 的数组 A ,求满足 0 ≤ a ≤ b < n 的 A[b] - A[a] 的最大值。
给定数组 A 及它的大小 n ,请返回最大差值。
数据范围: ,数组中的值满足
单调栈比较适合该题,大于栈顶进栈,否则出栈至栈顶小于当前元素再进栈.最大值就在进栈和遍历结束的时候
function getDis(A, n) { if (n <= 1) return 0; let stack = []; let max = 0; for (let i = 0; i < n; i++) { if (!stack.length) { stack.push(A[i]); } else { if (stack[stack.length - 1] < A[i]) { max = Math.max(max, A[i] - stack[0]); } else { while (stack.length) { if (stack[stack.length - 1] >= A[i]) { stack.pop(); } else { break; } } } stack.push(A[i]); } } if (stack.length) { max = Math.max(max, stack[stack.length - 1] - stack[0]); } return max; }